package medium括号生成;

import java.util.*;

public class Solution {

    public List<String> letterCombinations(int n) {
        List<String> combinations = new ArrayList<String>();
        String s = "()";
        if (n == 0) {
            return combinations;
        }
        backtrack(combinations, s, n, 0, new StringBuffer());
        List<String> list = new ArrayList<String>();
        for (int i = 0; i < combinations.size(); i++) {
            String s1 = combinations.get(i);

            for (int j = 0; j < n; j++) {
                s1=s1.replace("()", "");
            }
            if (s1.length() ==0){
                list.add(combinations.get(i));
            }
        }
        return list;
    }
    public void backtrack(List<String> combinations,String s, int n, int index, StringBuffer combination) {
        if (index == n*2 ) {
            combinations.add(combination.toString());
        }
        else {
            String letters = s;
            for (int i = 0; i < letters.length(); i++) {
                combination.append(letters.charAt(i));
                backtrack(combinations, s , n, index + 1, combination);
                combination.deleteCharAt(index);
            }
        }
    }
//    @Test
//    public void test(){
//        List<String> list = letterCombinations(2);
//
//        System.out.println(list.toString());
//        for (String s: list
//             ) {
//            System.out.println(s);
//        }
//    }// 2  6  22
}
